﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _002_选择排序
{
    class Program
    {
        static void Main(string[] args)
        {
            //int[] nums = { 76485156, 156, 1866, 32, 45, 98, 3, 46, 12, 878, 56487, 546, 31, 48, 35, 789, 345, 5478, 6541, 786, 3245, 41, 63, 33, 1 };
            //SelectSort(nums);
            //foreach (int i in nums)
            //{
            //    Console.WriteLine(i);
            //}

            //Console.ReadKey();

            TestPerformance();
            Console.ReadKey();
        }

        private static void TestPerformance()
        {
            Random random = new Random();
            int[] nums = new int[200000];
            for (int i = 0; i < 200000; i++)
            {
                nums[i] = random.Next(0, 10000000);
            }

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            //SelectSort(nums);
            DoubleSelectSort(nums);
            //BubbleSort(nums);
            stopwatch.Stop();
            long time = stopwatch.ElapsedMilliseconds;
            Console.WriteLine($"耗时:{time}毫秒");
            //foreach (int num in nums)
            //{
            //    Console.WriteLine(num);
            //}
        }

        private static int[] SelectSort(int[] nums)
        {
            int length = nums.Length;
            for (int i = 0; i < length-1; i++)
            {
                int minIndex = i;

                for (int j = i+1; j < length; j++)
                {
                    if (nums[minIndex]>nums[j])
                    {
                        minIndex = j;
                    }
                }

                if (minIndex!=i)
                {
                    int temp = nums[i];
                    nums[i] = nums[minIndex];
                    nums[minIndex] = temp;
                }
            }

            return nums;
        }
         
        private static int[] DoubleSelectSort(int[] nums)
        {
            int Length = nums.Length;
            for (int i = 0, j = Length - 1; i < Length / 2; i++, j--)
            {

                int minIndex = i; //最小值索引
                int maxIndex = i; //最大值索引

                //内层遍历一次产生一个最大值（右端）和最小值（左端），即从数组两端向中间产生有序元素
                for (int x = i + 1; x < Length - i; x++)
                {
                    if (nums[minIndex] > nums[x])
                    {
                        minIndex = x;
                        continue; //若当前元素是较小值直接遍历下个元素，不需要判断较大值
                    }
                    //当出现元素不是较小值时需要判断一下是否是较大值
                    else if (nums[maxIndex] < nums[x])
                    {
                        maxIndex = x;
                    }
                }

                int temp = 0;
                //当最大值索引指向最左端，且最小值索引指向最有端。将两数交换
                if (maxIndex == i && minIndex == j)
                {
                    temp = nums[maxIndex];
                    nums[maxIndex] = nums[minIndex];
                    nums[minIndex] = temp;
                }
                //当最大值索引指向最左端，提前将最大值与最右端交换。再将最小值与最左端交换。
                else if (maxIndex == i)
                {
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;

                    temp = nums[i];
                    nums[i] = nums[minIndex];
                    nums[minIndex] = temp;
                }
                //当最小值索引指向最右段，提前将最小值与最左端交换。再将最大值与最右端交换
                else if (minIndex == j)
                {
                    temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;

                    temp = nums[j];
                    nums[j] = nums[maxIndex];
                    nums[maxIndex] = temp;
                }
                //当最小值索引不是最左端时，交换
                else if (minIndex != i)
                {
                    temp = nums[i];
                    nums[i] = nums[minIndex];
                    nums[minIndex] = temp;
                    //当最大值索引不是最右端时，交换
                    if (maxIndex != j)
                    {
                        temp = nums[j];
                        nums[j] = nums[maxIndex];
                        nums[maxIndex] = temp;
                    }
                }
                //当最大值索引不是最右端时，交换
                else if (maxIndex != j)
                {
                    temp = nums[j];
                    nums[j] = nums[maxIndex];
                    nums[maxIndex] = temp;
                    //当最小值索引不是最左端时，交换
                    if (minIndex != i)
                    {
                        temp = nums[i];
                        nums[i] = nums[minIndex];
                        nums[minIndex] = nums[i];
                    }
                }
            }


            return nums;


        }

        private static int[] BubbleSort(int[] nums)
        {
            int length = nums.Length;
            for (int i = 0; i < length-1; i++)
            {
                for (int j = 0; j < length-1-i; j++)
                {
                    if (nums[j]>nums[j+1])
                    {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }

            return nums;
        }
    }
}
